﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
////给定一个头结点为 head 的非空单链表，返回链表的中间结点。
////如果有两个中间结点，则返回第二个中间结点。
////输入：[1, 2, 3, 4, 5]
////输出：此列表中的结点 3 (序列化形式：[3, 4, 5])
////返回的结点值为 3 。(测评系统对该结点序列化表述是[3, 4, 5])。
////注意，我们返回了一个 ListNode 类型的对象 ans，这样：
////ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
//
//
//  struct ListNode
//  {
//      int val;
//      struct ListNode *next;
//  };
// 
//struct ListNode* middleNode(struct ListNode* head) 
//{
//    struct ListNode* p = head;
//    struct ListNode* s = head;
//    while (p->next != NULL && p->next->next != NULL)
//    {
//        p = p->next->next;
//        s = s->next;
//    }
//    if (p->next != NULL)
//        s = s->next;
//    return s;
//}
//
////输入一个链表，输出该链表中倒数第k个结点。
////示例1
////输入：
////1, { 1,2,3,4,5 }
////复制
////返回值：
////{ 5 }
////
//
//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    // write code here
//    struct ListNode* f = pListHead;
//    struct ListNode* s = pListHead;
//    while (k--)
//    {
//        if (f == NULL)
//        {
//            return NULL;
//        }
//        f = f->next;
//    }
//    while (f)
//    {
//        f = f->next;
//        s = s->next;
//    }
//    return s;
//}
//
////将两个升序链表合并为一个新的 升序 链表并返回。
//// 新链表是通过拼接给定的两个链表的所有节点组成的。 
////
////示例 1：
////输入：l1 = [1, 2, 4], l2 = [1, 3, 4]
////输出：[1, 1, 2, 3, 4, 4]
//
//
// 
//  struct ListNode {
//      int val;
//     struct ListNode *next;
// };
// 
//
//
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
//    struct ListNode* phead = dummyHead, * q = list2, * temp = list2;
//    dummyHead->next = list1;
//    while (!(phead->next == NULL || q == NULL))
//    {
//        if (phead->next->val <= q->val)
//        {
//            phead = phead->next;
//        }
//        else
//        {
//            temp = q;
//            q = q->next;
//            temp->next = phead->next;
//            phead->next = temp;
//        }
//    }
//
//    if (q != NULL) {
//        phead->next = q;
//    }
//
//    return dummyHead->next;
//}

